#define _CRT_SECURE_NO_WARNINGS 1
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        for (int i = 0; i < nums.size() - 2; ++i)
        {
            if (i == 0 || nums[i] != nums[i - 1])
            {
                //printf("%d\n",i);
                int target = 0 - nums[i];
                int left = i + 1, right = nums.size() - 1;
                while (left < right)
                {
                    int lnum = nums[left], rnum = nums[right];
                    if (lnum + rnum > target)
                        --right;
                    else if (lnum + rnum < target)
                        ++left;
                    else
                    {
                        vector<int> v{ 0 - target,lnum,rnum };
                        // cout<<0-target<<endl;
                        // cout<<lnum<<endl;
                        // cout<<rnum<<endl;
                        ret.push_back(v);
                        while (left < right && nums[left] == nums[left + 1]) ++left;
                        while (left < right && nums[right] == nums[right - 1]) --right;
                        ++left;
                        --right;
                    }
                }
            }
        }
        return ret;
    }
};